#pragma once

#include "lims/entities/Point.hpp"
#include "lims/entities/Reference.hpp"
#include "lims/common/CalCirclePos.h"
#include "lims/common/Constants.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <chrono>

using namespace std;

namespace MetricSpaceBenchmark::MLIndex::LIMS {

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    class RangeQuery {
    public:

        unsigned N{};
        Point queryPoint;
        double radius{};
        double num_pow{};
        int num_pt{};

        RangeQuery();

        RangeQuery(Point &, double, mainRef_Point &, vector<int> &, CalCirclePos &, vector<CalCirclePos> &);

        int DoublingSearch(vector<double> &, bool, double, int);

        int BinarySearchForDoubling(vector<double> &, double, int, int);

        void DoRangeQuery(unsigned, vector<vector<int> > &, unsigned long long, mainRef_Point &, vector<int> &);

        double CaculateEuclideanDis(Point &, Point &);
    };
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    RangeQuery::RangeQuery() = default;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    RangeQuery::RangeQuery(Point &queryPoint, double radius, mainRef_Point &mainRef_point, vector<int> &rangeQueryRes,
                           CalCirclePos &mainRefPtCircle, vector<CalCirclePos> &ref_query) {
        // 获取该簇内的数据点个数（不重复）
        this->num_pt = mainRef_point.iValuePts.size();
        vector<vector<int> > rank_list;
        vector<int> mainRankRange;

        this->queryPoint = queryPoint;
        this->radius = radius;
        this->num_pow = pow(10, mainRef_point.ref_points.size() + 1);    // 偏序最大值（三个参考点就是1000，iValue最大就是 1000）

        // Plan B
        int len_dis = mainRef_point.dis.size();
        int split = ceil((double) len_dis / Constants::NUM_CIRCLE);

        unsigned refPtSize = mainRef_point.ref_points.size();

        rank_list.resize(refPtSize + 1);
        mainRankRange.resize(2);

        // use polynomial regression model
        // 多项式拟合的最大最小误差
        double mainRefPre_disLower = mainRef_point.coeffs[0];
        double mainRefPre_disUpper = mainRef_point.coeffs[0];
        for (int i = 1; i <= Constants::COEFFS; ++i) {
            mainRefPre_disLower += mainRef_point.coeffs[i] * pow(mainRefPtCircle.dis_lower, i);
            mainRefPre_disUpper += mainRef_point.coeffs[i] * pow(mainRefPtCircle.dis_upper, i);
        }
        // 取整
        int mainRefPrePos_lower = mainRefPre_disLower;
        int mainRefPrePos_upper = mainRefPre_disUpper;

        if (mainRefPrePos_lower < 0)
            mainRefPrePos_lower = 0;
        if (mainRefPrePos_lower >= len_dis)
            mainRefPrePos_lower = len_dis - 1;

        int pred_lower = 0;

        if (mainRef_point.dis[mainRefPrePos_lower] == mainRefPtCircle.dis_lower) {
            pred_lower = mainRefPrePos_lower;
        } else if (mainRef_point.dis[mainRefPrePos_lower] > mainRefPtCircle.dis_lower) {
            pred_lower = DoublingSearch(mainRef_point.dis, true, mainRefPtCircle.dis_lower, mainRefPrePos_lower);
        } else {
            pred_lower = DoublingSearch(mainRef_point.dis, false, mainRefPtCircle.dis_lower, mainRefPrePos_lower);
        }

        if (mainRef_point.dis[pred_lower] >= mainRefPtCircle.dis_lower)
            mainRankRange[0] = pred_lower / split;
        else
            mainRankRange[0] = (pred_lower + 1) / split;

        if (mainRefPrePos_upper < 0)
            mainRefPrePos_upper = 0;
        if (mainRefPrePos_upper >= len_dis)
            mainRefPrePos_upper = len_dis - 1;

        int pred_upper = 0;

        if (mainRef_point.dis[mainRefPrePos_upper] == mainRefPtCircle.dis_upper) {
            pred_upper = mainRefPrePos_upper;
        } else if (mainRef_point.dis[mainRefPrePos_upper] > mainRefPtCircle.dis_upper) {
            pred_upper = DoublingSearch(mainRef_point.dis, true, mainRefPtCircle.dis_upper, mainRefPrePos_upper);
        } else {
            pred_upper = DoublingSearch(mainRef_point.dis, false, mainRefPtCircle.dis_upper, mainRefPrePos_upper);
        }

        if (mainRef_point.dis[pred_upper] > mainRefPtCircle.dis_upper)
            mainRankRange[1] = (pred_upper - 1) / split;
        else
            mainRankRange[1] = pred_upper / split;

        rank_list[0] = mainRankRange;

        for (unsigned i = 0; i < refPtSize; ++i) {

            vector<int> refRankRange;
            refRankRange.resize(2);

            double refPre_disLower = mainRef_point.ref_points[i].coeffs[0];
            double refPre_disUpper = mainRef_point.ref_points[i].coeffs[0];
            for (int j = 1; j <= Constants::COEFFS; ++j) {
                refPre_disLower += mainRef_point.ref_points[i].coeffs[j] * pow(ref_query[i].dis_lower, j);
                refPre_disUpper += mainRef_point.ref_points[i].coeffs[j] * pow(ref_query[i].dis_upper, j);
            }

            int refPrePos_lower = refPre_disLower;
            int refPrePos_upper = refPre_disUpper;

            if (refPrePos_lower < 0)
                refPrePos_lower = 0;
            if (refPrePos_lower >= len_dis)
                refPrePos_lower = len_dis - 1;

            int refPred_lower = 0;

            if (mainRef_point.ref_points[i].dis[refPrePos_lower] == ref_query[i].dis_lower) {
                refPred_lower = refPrePos_lower;

            } else if (mainRef_point.ref_points[i].dis[refPrePos_lower] > ref_query[i].dis_lower) {
                refPred_lower = DoublingSearch(mainRef_point.ref_points[i].dis, true, ref_query[i].dis_lower,
                                               refPrePos_lower);
            } else {
                refPred_lower = DoublingSearch(mainRef_point.ref_points[i].dis, false, ref_query[i].dis_lower,
                                               refPrePos_lower);
            }

            if (mainRef_point.ref_points[i].dis[refPred_lower] >= ref_query[i].dis_lower)
                refRankRange[0] = refPred_lower / split;
            else
                refRankRange[0] = (refPred_lower + 1) / split;

            if (refPrePos_upper < 0)
                refPrePos_upper = 0;
            if (refPrePos_upper >= len_dis)
                refPrePos_upper = len_dis - 1;

            int refPred_upper = 0;

            if (mainRef_point.ref_points[i].dis[refPrePos_upper] == ref_query[i].dis_upper) {
                refPred_upper = refPrePos_upper;
            } else if (mainRef_point.ref_points[i].dis[refPrePos_upper] > ref_query[i].dis_upper) {
                refPred_upper = DoublingSearch(mainRef_point.ref_points[i].dis, true, ref_query[i].dis_upper,
                                               refPrePos_upper);
            } else {
                refPred_upper = DoublingSearch(mainRef_point.ref_points[i].dis, false, ref_query[i].dis_upper,
                                               refPrePos_upper);
            }

            if (mainRef_point.ref_points[i].dis[refPred_upper] > ref_query[i].dis_upper)
                refRankRange[1] = (refPred_upper - 1) / split;
            else
                refRankRange[1] = refPred_upper / split;


            rank_list[i + 1] = refRankRange;
        }


        int n = 1;
        while (n <= Constants::NUM_CIRCLE - 1)
            n *= 10;
        this->N = n;

        unsigned i = 0;
        unsigned long long queryRange = 0;


        DoRangeQuery(i, rank_list, queryRange, mainRef_point, rangeQueryRes);
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /* 指数搜索
     * param 1 : list
     * param 2 : search forward(true) / search backward(false)
     * param 3 : target value
     */
    int RangeQuery::DoublingSearch(vector<double> &disList, bool flag, double target, int start) {
        // 获取距离列表 disList 的长度,用于后续判断索引边界等操作,确保搜索过程不会超出列表范围
        int len = disList.size();
        // 如果搜索方向标志 flag 为 true,表示向前搜索(从起始位置向列表头部方向搜索),进入以下逻辑
        if (flag) {
            // 如果起始位置start就是0,说明已经在列表开头了,直接返回0作为目标值的位置(因为没有更靠前的位置可找了)
            if (start == 0)
                return 0;
            // 初始化一个变量k,用于控制每次搜索步长的倍增,初始值设为1,后续会不断左移(乘以2)来增大搜索步长
            int k = 1;
            // 将起始位置start的值赋给end,初始化end变量,表示当前搜索区间的末尾位置,后续会根据搜索情况动态变化
            int end = start;
            // 只要当前搜索区间末尾位置end对应的距离值大于目标值target,就继续循环调整搜索区间,进行倍增搜索
            while (disList[end] > target) {
                // 将当前搜索区间末尾位置end的值赋给start,更新搜索区间的起始位置,准备缩小搜索区间
                start = end;
                // 根据倍增步长k,将end向前移动(减去k),缩小搜索区间,往目标值所在方向靠近
                end -= k;
                // 将搜索步长k进行倍增,通过左移一位(相当于乘以2)来增大下次搜索的步长,加快搜索速度
                k = k << 1;
                // 如果移动后的end小于0,说明已经超出列表头部范围了,将end设置为0(最前端位置),并跳出循环,避免越界访问
                if (end < 0) {
                    end = 0;
                    break;
                }
            }
            // 如果经过上述搜索后,当前搜索区间末尾位置end对应的距离值恰好等于目标值target,直接返回end作为目标值的位置索引
            if (disList[end] == target)
                return end;
            // 如果搜索区间缩小到只有一个位置(即start和end相等),并且这个位置就是列表开头(start == 0),说明没有找到目标值但已经到最前端了,返回0作为目标值的大致位置(可能后续会通过更精确的查找进一步确定)
            if (start == end && start == 0)
                return 0;
            // 如果没有直接找到目标值,调用 BinarySearchForDoubling 函数在当前确定的大致区间(从end到start)内进行二分查找,进一步精确确定目标值的准确位置,并返回最终找到的位置索引
            return BinarySearchForDoubling(disList, target, end, start);
        } else {    // 如果搜索方向标志 flag 为 false,表示向后搜索(从起始位置向列表尾部方向搜索),进入以下逻辑
            // 如果起始位置start已经是列表的最后一个位置(len - 1),说明已经在列表末尾了,直接返回len - 1作为目标值的位置(因为没有更靠后的位置可找了)
            if (start == len - 1)
                return len - 1;
            // 初始化一个变量k,用于控制每次搜索步长的倍增,初始值设为1,后续会不断左移(乘以2)来增大搜索步长,和向前搜索时的作用类似但方向相反
            int k = 1;
            // 将起始位置start的值赋给end,初始化end变量,表示当前搜索区间的末尾位置,后续会根据搜索情况动态变化
            int end = start;
            // 只要当前搜索区间末尾位置end对应的距离值小于目标值target,就继续循环调整搜索区间,进行倍增搜索
            while (disList[end] < target) {
                // 将当前搜索区间末尾位置end的值赋给start,更新搜索区间的起始位置,准备缩小搜索区间
                start = end;
                // 根据倍增步长k,将end向后移动(加上k),缩小搜索区间,往目标值所在方向靠近
                end += k;
                // 将搜索步长k进行倍增,通过左移一位(相当于乘以2)来增大下次搜索的步长,加快搜索速度
                k = k << 1;
                // 如果移动后的end大于列表长度减1(超出列表尾部范围),将end设置为len - 1(最后端位置),并跳出循环,避免越界访问
                if (end > len - 1) {
                    end = len - 1;
                    break;
                }
            }
            // 如果经过上述搜索后,当前搜索区间末尾位置end对应的距离值恰好等于目标值target,直接返回end作为目标值的位置索引
            if (disList[end] == target)
                return end;
            // 如果搜索区间缩小到只有一个位置(即start和end相等),并且这个位置就是列表末尾 (start == len - 1),说明没有找到目标值但已经到最后端了,返回len - 1作为目标值的大致位置(可能后续会通过更精确的查找进一步确定)
            if (start == end && start == len - 1)
                return len - 1;
            // 如果没有直接找到目标值,调用BinarySearchForDoubling函数在当前确定的大致区间(从start到end)内进行二分查找,进一步精确确定目标值的准确位置,并返回最终找到的位置索引
            return BinarySearchForDoubling(disList, target, start, end);
        }
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    int RangeQuery::BinarySearchForDoubling(vector<double> &disList, double target, int low, int high) {
        // 初始化中间位置索引为0,后续在循环中会不断更新这个中间位置来逼近目标值(target)在指定区间内的准确位置
        int middle = 0;
        // 只要查找区间的下限low不超过上限high,就继续进行二分查找循环,不断缩小查找范围来确定目标值的准确位置
        while (low <= high) {
            // 计算当前查找区间(从low到high)的中间位置索引,采用这种计算方式((high - low) / 2 + low)可以避免整数溢出等问题(相较于简单的 (low + high) / 2),得到当前查找区间内的中间位置
            middle = (high - low) / 2 + low;
            // 如果目标值小于中间位置middle对应的距离值(即disList[middle]),说明目标值在左半部分,更新查找范围的上限为中间位置减1,缩小查找范围到左半区间继续查找
            if (target < disList[middle]) {
                high = middle - 1;
            } else if (target > disList[middle]) {    // 如果目标值大于中间位置middle对应的距离值,说明目标值在右半部分,更新查找范围的下限为中间位置加1,缩小查找范围到右半区间继续查找
                low = middle + 1;
            } else { // 如果目标值等于中间位置middle对应的距离值,还需要进一步判断是否是目标值出现的起始位置(因为可能存在重复值)
                // 如果中间位置middle大于0且前一个位置的距离值小于目标值(即找到目标值首次出现的位置,也就是起始位置),或者中间位置就是0(说明是列表开头,那就是起始位置了),则找到目标位置,跳出循环
                if ((middle > 0 && disList[middle - 1] < target) || (middle == 0)) {        //找到开始位置
                    break;
                } else {
                    high = middle - 1;    // 如果不是目标值首次出现的位置,那就继续缩小查找范围到左半区间(因为要找起始位置),更新上限为中间位置减1
                }
            }
        }
        // 返回最终确定的目标值在指定区间内的位置索引
        return middle;
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    void RangeQuery::DoRangeQuery(unsigned i, vector<vector<int> > &rank_list, unsigned long long queryRange,
                                  mainRef_Point &mainRef_point, vector<int> &rangeQueryRes) {
        if (i == rank_list.size() - 1) {
            unsigned long long query_lower = queryRange * N + rank_list[i][0];
            unsigned long long query_upper = queryRange * N + rank_list[i][1];

            double x_lower = query_lower / num_pow;
            double x_upper = query_upper / num_pow;
            int CaculY_lower = (int) (mainRef_point.a * x_lower + mainRef_point.b);
            int CaculY_upper = (int) (mainRef_point.a * x_upper + mainRef_point.b);
            unsigned long long find_queryLower;
            int pos_lower;
            unsigned long long find_queryUpper;
            int pos_upper;

            // Binary search for the first one which >= query_lower
            int low = CaculY_lower - mainRef_point.err_min < 0 ? 0 : CaculY_lower - mainRef_point.err_min;
            low = low > num_pt - 1 ? num_pt - 1 : low;
            int high = CaculY_lower + mainRef_point.err_max < num_pt ? CaculY_lower + mainRef_point.err_max : num_pt - 1;
            int middle = 0;

            while (low <= high) {
                middle = (high - low) / 2 + low;
                if (query_lower < mainRef_point.iValuePts[middle].i_value)
                    high = middle - 1;
                else if (query_lower > mainRef_point.iValuePts[middle].i_value)
                    low = middle + 1;
                else  //mid=target
                {
                    if ((middle > 0 && mainRef_point.iValuePts[middle - 1].i_value < query_lower) || (middle == 0))//找到开始位置
                    {
                        break;
                    } else
                        high = middle - 1;
                }
            }

            if (middle < low && low < num_pt) {
                pos_lower = low;
                find_queryLower = mainRef_point.iValuePts[low].i_value;
            } else {
                pos_lower = middle;
                find_queryLower = mainRef_point.iValuePts[middle].i_value;
            }

            // Binary search for the last one which <= query_upper
            low = CaculY_upper - mainRef_point.err_min < 0 ? 0 : CaculY_upper - mainRef_point.err_min;
            low = low > num_pt - 1 ? num_pt - 1 : low;
            high = CaculY_upper + mainRef_point.err_max < num_pt ? CaculY_upper + mainRef_point.err_max : num_pt - 1;
            middle = 0;

            while (low <= high) {
                middle = (high - low) / 2 + low;
                if (mainRef_point.iValuePts[middle].i_value > query_upper)
                    high = middle - 1;
                else if (mainRef_point.iValuePts[middle].i_value < query_upper)
                    low = middle + 1;
                else  //mid=target
                {
                    if ((middle < num_pt - 1 && mainRef_point.iValuePts[middle + 1].i_value > query_upper) ||
                        (middle == num_pt - 1))//找到结束位置
                    {
                        break;
                    } else
                        low = middle + 1;
                }
            }
            if (query_upper == mainRef_point.iValuePts[middle].i_value) {
                pos_upper = middle;
                find_queryUpper = query_upper;
            } else if (middle < low) {
                pos_upper = low - 1;
                find_queryUpper = mainRef_point.iValuePts[low - 1].i_value;
            } else {
                if (middle == 0) {
                    pos_upper = 0;
                    find_queryUpper = mainRef_point.iValuePts[0].i_value;
                } else {
                    pos_upper = middle - 1;
                    find_queryUpper = mainRef_point.iValuePts[middle - 1].i_value;
                }
            }

            if (find_queryLower >= find_queryUpper) {
                if (find_queryLower == find_queryUpper && find_queryLower >= query_lower &&
                    find_queryUpper <= query_upper) {
                    for (int x = pos_lower; x <= pos_upper; ++x) {
                        // this->result.push_back(mainRef_point.iValuePts[x]);
                        if (CaculateEuclideanDis(mainRef_point.iValuePts[x], queryPoint) <= radius)
                            rangeQueryRes.push_back(mainRef_point.iValuePts[x].id);
                    }
                }
            } else {
                for (int x = pos_lower; x <= pos_upper; ++x) {
                    // this->result.push_back(mainRef_point.iValuePts[x]);
                    if (CaculateEuclideanDis(mainRef_point.iValuePts[x], queryPoint) <= radius)
                        rangeQueryRes.push_back(mainRef_point.iValuePts[x].id);
                }
            }
        } else {
            for (int j = rank_list[i][0]; j <= rank_list[i][1]; ++j) {
                queryRange = queryRange * N + j;

                DoRangeQuery(++i, rank_list, queryRange, mainRef_point, rangeQueryRes);
                i--;

                queryRange = (int) queryRange / N;
            }
        }
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    double RangeQuery::CaculateEuclideanDis(Point &point_a, Point &point_b) {
        double total = 0.0;
        unsigned dim = point_a.coordinate.size();
        for (unsigned i = 0; i < dim; ++i) {
            total += pow(point_a.coordinate[i] - point_b.coordinate[i], 2);
        }
        return sqrt(total);
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}